#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <utility>
#include <vector>

using namespace std;

class Solution {
  public:
    vector<int> findSubstring(string s, vector<string> &words)
    {
        /*
            将所有的单词拼接排列，获取所有可能排列，之后，全量匹配 --
           全排列的处理复杂度太高

            双指针法，一个指针遍历主串，一个指针遍历单词组
            主串的匹配可以按照单词的长度，按某个单词进行匹配
        */
        int         length = words[0].size();
        vector<int> result;

        map<string, int> match;
        for (int i = 0; i < words.size(); i++) {
            // match.insert(make_pair(words[i], true));
            if (match.find(words[i]) == match.end()) {
                match[words[i]] = 1;
            } else {
                match[words[i]]++;
            }
        }

        int iter = 0;
        while (iter < s.size()) {
            map<string, int> copiedMatch = match;

            int start = iter;
            while (!copiedMatch.empty() && iter < s.size()) {
                string                     tmp  = s.substr(iter, length);
                map<string, int>::iterator find = copiedMatch.find(tmp);
                if (find == copiedMatch.end()) {
                    // cannot, not match
                    if (match.find(tmp) == match.end()) {
                        // not in match
                        iter += length;
                    }
                    break;
                }
                if (find->second == 1) {
                    copiedMatch.erase(tmp);
                } else {
                    copiedMatch[tmp]--;
                }
                iter += length;
            }
            if (copiedMatch.empty()) {
                result.push_back(start);
            }
            iter = start + 1;
        }

        return result;
    }
};

void testcase01()
{
    printf("%s test begin...\n", __FUNCTION__);
    string         inputMaster = "barfoothefoobarman";
    vector<string> inputPattern;
    inputPattern.push_back("foo");
    inputPattern.push_back("bar");
    vector<int> got;
    // vector<int> want;

    Solution so;
    got = so.findSubstring(inputMaster, inputPattern);
    for (int i = 0; i < got.size(); i++) {
        printf("get %d\n", got[i]);
    }
}
void testcase02()
{
    printf("%s test begin...\n", __FUNCTION__);
    string         inputMaster = "wordgoodgoodgoodbestword";
    vector<string> inputPattern;
    inputPattern.push_back("word");
    inputPattern.push_back("good");
    inputPattern.push_back("best");
    inputPattern.push_back("word");
    vector<int> got;

    Solution so;
    got = so.findSubstring(inputMaster, inputPattern);
    for (int i = 0; i < got.size(); i++) {
        printf("get %d\n", got[i]);
    }
}
void testcase03()
{
    printf("%s test begin...\n", __FUNCTION__);
    string         inputMaster = "barfoofoobarthefoobarman";
    vector<string> inputPattern;
    inputPattern.push_back("bar");
    inputPattern.push_back("foo");
    inputPattern.push_back("the");
    vector<int> got;

    Solution so;
    got = so.findSubstring(inputMaster, inputPattern);
    for (int i = 0; i < got.size(); i++) {
        printf("get %d\n", got[i]);
    }
}

void testcase04()
{
    printf("%s test begin...\n", __FUNCTION__);
    string inputMaster = "lingmindraboofooowingdingbarrwingmonkeypoundcake";
    vector<string> inputPattern;
    inputPattern.push_back("fooo");
    inputPattern.push_back("barr");
    inputPattern.push_back("wing");
    inputPattern.push_back("ding");
    inputPattern.push_back("wing");
    vector<int> got;

    Solution so;
    got = so.findSubstring(inputMaster, inputPattern);
    for (int i = 0; i < got.size(); i++) {
        printf("get %d\n", got[i]);
    }
}
int main()
{
    testcase01();
    testcase02();
    testcase03();
    testcase04();
    return 0;
}